package club.xiaojiawei.linkedlist;


/**
 * @author 肖嘉威
 * @version 1.0
 * @date 2022/4/22 22:32
 * @question 206.反转链表
 * @description 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */
public class ReverseLinkedList206 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        ListNode listNode = reverseList(head);
//        ListNode listNode = reverseList2(head);
        System.out.println(listNode);
    }

    /**
     * 迭代-蜘蛛纸牌
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode temp = head;
        ListNode newHead = null;
        ListNode middle;
        while (temp != null){
            middle = temp.next;
            temp.next = newHead;
            newHead = temp;
            temp = middle;
        }
        return newHead;
    }

    /**
     * 递归
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        if (head.next != null){
            ListNode node = reverseList2(head.next);
            head.next.next = head;
            head.next = null;
            return node;
        }else {
            return head;
        }
    }


    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    '}';
        }
    }
}
